package 算法.练习1;

import 算法.NiuKe.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

/**
 * @author:谢君臣
 * @Date:2021/7/20-14:27
 * @version:1.0
 * @function:
 */
public class NC15 {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        Queue<TreeNode> stack1 = new ArrayDeque<>();
        if (root==null)
            return new ArrayList<>();
        else {
            stack1.add(root);
            return getList(stack1);
        }
    }

    private ArrayList<ArrayList<Integer>> getList(Queue<TreeNode> stack1) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Queue<TreeNode> stack2 = new ArrayDeque<>();
        while (!stack1.isEmpty()||!stack2.isEmpty()){
            ArrayList<Integer> temp = new ArrayList<>();
            if (!stack1.isEmpty()){
                while (!stack1.isEmpty()){
                    TreeNode pop = stack1.poll();
                    if (pop.left!=null) stack2.add(pop.left);
                    if (pop.right!=null) stack2.add(pop.right);
                    temp.add(pop.val);
                }
            }else {
                while (!stack2.isEmpty()){
                    TreeNode pop = stack2.poll();
                    if (pop.left!=null) stack1.add(pop.left);
                    if (pop.right!=null) stack1.add(pop.right);
                    temp.add(pop.val);
                }
            }
            res.add(temp);
        }
        return res;
    }
}
